/*
 * @Author: szx
 * @Date: 2022-01-27 14:43:25
 * @LastEditTime: 2022-01-27 15:04:29
 * @Description:
 * @FilePath: \leetcode\500-599\516\516.js
 */
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    // dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
    const n = s.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    for (let i = 0; i < n; i++) dp[i][i] = 1;
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
};
console.log(longestPalindromeSubseq('bbbab'));

var longestPalindromeSubseq = function (s) {
    // dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
    const n = s.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] == s[j]) {
                if (i == j) dp[i][j] = 1;
                else dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
};
